﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0049_Combine : IAlgorithm
    {
        // 77. 组合

        // 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

        // 你可以按 任何顺序 返回答案。

        // 提示：
        //  1 <= n <= 20
        //  1 <= k <= n

        public void Test()
        {
            // 算法参数定义
            int n = 4, k = 3;
            // 算法执行与打印
            var result = Combine1(n, k);
            foreach (var row in result)
            {
                foreach (var item in row)
                {
                    Console.Write(item + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public IList<IList<int>> Combine(int n, int k)
        {
            return Combine(1, n, k);
        }

        private IList<IList<int>> Combine(int s, int n, int k)
        {
            var result = new List<IList<int>>();
            if (k == 1)
                for (int i = s; i <= n; i++)
                    result.Add(new List<int>() { i });
            else
                for (int i = s; i <= n - k + 1; i++)
                {
                    var nextList = Combine(i + 1, n, k - 1);
                    foreach (var row in nextList)
                    {
                        var tempList = new List<int>() { i };
                        foreach (var item in row)
                            tempList.Add(item);
                        result.Add(tempList);
                    }
                }
            return result;
        }

        // 回溯+DFS+剪枝
        public IList<IList<int>> Combine1(int n, int k)
        {
            var res = new List<IList<int>>();
            if (k <= 0 || n < k)
                return res;
            Stack<int> path = new Stack<int>();
            DFS(n, k, 1, path, res);
            return res;
        }
        private void DFS(int n, int k, int index, Stack<int> path, IList<IList<int>> res)
        {
            if (path.Count == k)
                res.Add(path.ToList());
            else
                for (int i = index; i <= n - (k - path.Count) + 1; i++)
                {
                    path.Push(i);
                    DFS(n, k, i + 1, path, res);
                    path.Pop();
                }
        }
    }
}
